package leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wangmaolin1
 * @date 2023/11/11 11:32
 */
public class _106 {
    private Map<Integer, Integer> inorderRootVal2Index = new HashMap<>();

    /**
     * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
     * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
     * 输出：[3,9,20,null,null,15,7]
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderRootVal2Index.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    /**
     * 1. 找根节点
     * 后序遍历的最后一个元素
     * 2.确认左右子树范围
     * 中序的左子树：inStart:rootIndex-1
     * 中序的右子树：rootIndex+1,inEnd
     * 后序的左子树：postStart,(postStart + 左子树节点个数 - 1) -> plEnd
     * 后序的右子树:plEnd+1,postEnd-1
     */
    public TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || inEnd>=inorder.length || postStart>postEnd || postEnd>=postorder.length){
            return null;
        }
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        Integer rootIndex = inorderRootVal2Index.get(rootVal);
        int leftTreeNodeNum = rootIndex - inStart;
        root.left = build(inorder,inStart,rootIndex-1,postorder,postStart,postStart+leftTreeNodeNum-1);
        root.right = build(inorder,rootIndex+1,inEnd,postorder,postStart+leftTreeNodeNum,postEnd-1);
        return root;
    }
}
